import requests
from gmpy2 import *
from libnum import *

def factorize(n):
    l = []
    url="http://factordb.com/api?query="+str(n)
    r = requests.get(url)
    data = r.json()   
    for factor in data['factors']:
        for i in range(int(factor[1])):
            l.append(int(factor[0]))
    return l

def rational_to_contfrac(x,y):
    '''
    Converts a rational x/y fraction into
    a list of partial quotients [a0, ..., an]
    '''
    a = x//y
    pquotients = [a]
    while a * y != x:
        x,y = y,x-a*y
        a = x//y
        pquotients.append(a)
    return pquotients

def contfrac_to_rational (frac):
    '''Converts a finite continued fraction [a0, ..., an]
     to an x/y rational.
     '''
    if len(frac) == 0:
        return (0,1)
    num = frac[-1]
    denom = 1
    for _ in range(-2,-len(frac)-1,-1):
        num, denom = frac[_]*num+denom, num
    return (num,denom)

# efficient method that calculates convergents on-the-go, without doing partial quotients first
def convergents_from_contfrac(frac):
    '''
    computes the list of convergents
    using the list of partial quotients
    '''
    convs = [];
    for i in range(len(frac)):
        convs.append(contfrac_to_rational(frac[0:i]))
    return convs

def bitlength(x):
    '''
    Calculates the bitlength of x
    '''
    assert x >= 0
    n = 0
    while x > 0:
        n = n+1
        x = x>>1
    return n

def isqrt(n):
    '''
    Calculates the integer square root
    for arbitrary large nonnegative integers
    '''
    if n < 0:
        raise ValueError('square root not defined for negative numbers')
    if n == 0:
        return 0
    a, b = divmod(bitlength(n), 2)
    x = 2**(a+b)
    while True:
        y = (x + n//x)//2
        if y >= x:
            return x
        x = y

def is_perfect_square(n):
    '''
    If n is a perfect square it returns sqrt(n),
    otherwise returns -1
    '''
    h = n & 0xF; #last hexadecimal "digit"
    if h > 9:
        return -1 # return immediately in 6 cases out of 16.
    # Take advantage of Boolean short-circuit evaluation
    if ( h != 2 and h != 3 and h != 5 and h != 6 and h != 7 and h != 8 ):
        # take square root if you must
        t = isqrt(n)
        if t*t == n:
            return t
        else:
            return -1
    return -1

def hack_RSA(e,n):
    '''
    Finds d knowing (e,n)
    applying the Wiener continued fraction attack
    '''
    frac = rational_to_contfrac(e, n)
    convergents = convergents_from_contfrac(frac)
    
    for (k,d) in convergents:
        
        #check if d is actually the key
        if k!=0 and (e*d-1)%k == 0:
            phi = (e*d-1)//k
            s = n - phi + 1
            # check if the equation x^2 - s*x + n = 0
            # has integer roots
            discr = s*s - 4*n
            if(discr>=0):
                t = is_perfect_square(discr)
                if t!=-1 and (s+t)%2==0:
                    print("Hacked!")
                    return d

def level1():
    e = 0x10001
    c = 22160015525054597533062795679117215923801827397299805735087138192137742945881204146337349060934854888054628153923021387981306839951210090523829296521835965212118849043671673133979884712755090374758002677916820953359774554825569218497687506468472278309097929775388010403607769802840990547048001743970754496905
    p = 6962443023774446497102092246794613339314677593117417573764609329949026862782472380488956732038459060928443992561763464365758383525259954798321350043810351
    q = 9631855759661411029901156175243744760977799976661519182223576693685069000499866459636568713055906075171480855575061732016121299027658733834671035383233163
    n = p*q
    d = invmod(e, (p-1)*(q-1)) 
    m = pow(c, d, n)  # m = c^d%n
    flag = n2s(m).decode('utf-8')
    return flag # flag{W0w_

def level2():
    e = 0x10001
    c = 17250922799297131008803303235771955129
    n = 134097988095851988085603926250918812377
    q, p = factorize(n)
    d = invmod(e, (p-1)*(q-1))
    m = pow(c, d, n)
    flag = n2s(m).decode()
    return flag # U_ar3_re4

def level3():
    e = 3
    c = 2776571135646565181849912433877522437622755332262910824866791711
    n = 85793694792655420934945863688968944466300304898903354212780512650924132933351787673979641944071634528676901506049360194331553838080226562532784448832916022442020751986591703547743056267118831445759258041047213294368605599719242059474324548598203039032847591828382166845797857139844445858881218318006747115157
    i = 0
    while True:
        m, ok = iroot(c+i*n, e)
        if ok:
            flag = n2s(int(m)).decode()
            break
        i += 1
    return flag # L1y_g0Od_

def level4():
    c = 68588738085497640698861260094482876262596289469248772328560280530093163764972313090939471997156632421517452790632223565521726590730640805290182026911025142051864898712501214753986865172996090706657535814234291235489829621372021092488300236623525366939477695283380634188510950335639019458758643273802572617191
    e = 51999725233581619348238930320668315462087635295211755849675812266270026439521805156908952855288255992098479180003264827305694330542325533165867427898010879823017054891520626992724274019277478717788189662456052796449734904215067032681345261878977193341769514961038309763898052908572726913209883965288047452751
    n = 68816697240190744603903822351423855593899797203703723038363240057913366227564780805815565183450516726498872118491739132110437976570592602837245705802946829337567674506561850972973663435358068441037127926802688722648016352967768929007662772115485020718202683004813042834036078650571763978066558718285783045969
    d = hack_RSA(e, n) # 12966126097163765179
    m = pow(c, d, n)
    flag = n2s(m).decode()
    return flag # 4t_m4th_4

def level5():
    e = 0x10001
    c = 1135954814335407362237156338232840769700916726653557860319741136149066730262056907097728029957898420630256832277578506404721904131425822963948589774909272408535427656986176833063600681390871582834223748797942203560505159946141171210061405977060061656807175913366911284450695116982731157917343650021723054666494528470413522258995220648163505549701953152705111304471498547618002847587649651689203632845303117282630095814054989963116013144483037051076441508388998829
    hint = 611144874477135520868450203622074557606421849009025270666985817360484127602945558050689975570970227439583312738313767886380304814871432558985582586031211416586296452510050692235459883608453661597776103386009579351911278185434163016083552988251266501525188362673472772346212970459561496301631587043106524741903627979311997541301471894670374945556313285203740782346029579923650160327646876967315182335114575921178144825057359851607166387868294019144940296084605930
    n = 1232865496850144050320992645475166723525103370117149219196294373695624167653495180701004894188767069545579706264513808335877905149818445940067870026924895990672091745229251935876434509430457142930654307044403355838663341948471348893414890261787326255632362887647279204029327042915224570484394917295606592360109952538313570951448278525753313335289675455996833500751672463525151201002407861423542656805624090223118747404488579783372944593022796321473618301206064979
    l = factorize(n)
    q, p = l[0], l[2]
    d = invmod(e, p*(p-1)*(q-1))
    m = pow(c, d, n)
    flag = n2s(m).decode()
    return flag # nD_RSA!!}

flag = level1()+level2()+level3()+level4()+level5()
print(flag) # flag{W0w_U_ar3_re4L1y_g0Od_4t_m4th_4nD_RSA!!}